1. Authorization Pursuant to 37 C.F.R. 1.71(e)
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
2. Field of the Invention
The field of the present invention relates generally to content addressable memories (CAMs), and more particularly to CAM cells for constructing high-speed, large-capacity CAM arrays with fill bit-wise and word-wise masking capability.
3. Related Art
A content addressable memory (CAM) is an associative memory device in which memory elements are identified (i.e. addressed) by their content, rather than by their physical location. A CAM generally includes a matrix of CAM cells arranged in rows and columns. Each CAM cell in this matrix usually includes a static memory element and comparison circuitry.
Typical uses for CAMs include pattern-matching memories for optical character recognition, and translation look-aside buffers for digital computers that employ virtual memory. In a traditional CAM, each CAM cell stores one bit of digital information in the static memory element. In some CAMs, each CAM cell employs xe2x80x9cdual endedxe2x80x9d logic, such that the cell makes available both a stored bit and its inverse. The static memory elements are connected with differential bit lines and a word line, thereby allowing read and write data operations. Typically, the comparison circuitry in each CAM cell is connected with separate differential compare bit lines, thus creating more flexibility in the timing of read, write and search operations.
An array of CAM cells, commonly arranged in a row, comprise a word of data. During a search operation, the CAM compares a search word (comparand) with a set of words stored within the CAM. One or more indicators associated with each word of data, commonly called match lines, produce a comparison result, which identifies the word(s) in the CAM that match the comparand. Thus a CAM usually requires more transistors and/or other circuit elements than standard Random Access Memory (RAM), but adds a xe2x80x9cparallel processingxe2x80x9d characteristic not found in a standard RAM.
One common use of a CAM is as a search tool for network address filtering. Network address filtering is a process for searching a router""s station list for source and destination addresses and routing packets to the correct port(s). Modern telecommunication networks typically use digital packet or block type data formats as a means for dynamically routing data through a network. The advantages of such dynamically routed packetized data are well known. However, as data transfer rates continue to increase, the finite processing power available at network routers can cause communication bottlenecks, where data packets arrive faster than the router can determine where to route the incoming packets. Such bottlenecks can easily degrade the overall performance of a network.
A CAM can reduce processing bottlenecks by increasing the speed at which routing can be accomplished. Typical packet-based communication networks utilize digital xe2x80x9cheaderxe2x80x9d information at the beginning of each packet in the routing process. This header information comprises address fields defining source and destination information. Long addresses are necessary to accommodate the large number of potential addresses common in modern communication networks. These long addresses can substantially increase the time required to make routing decisions, thus requiring a fast searching technique during network address filtering. A CAM generally achieves this search performance by simultaneously comparing all entries stored in the CAM with a xe2x80x9ccomparand.xe2x80x9d
FIG. 1 is a schematic block diagram illustrating a simple example of a conventional content addressable memory (CAM) utilizing dual-ended logic, with enlargements illustrating further details of a CAM cell and a CAM memory core cell. In FIG. 1, a CAM 100 is shown with only four rows and four columns, for a total of 16 CAM cells 110, whereas in most practical applications the CAM would have many more CAM cells. Each row corresponds to a word, or part of a word, of data. Each column corresponds to a bit of data from each row or word. Each CAM cell 110 in a column is coupled with a local pair of bit lines 112 (b and bn) and a local pair of compare lines 114 (k and kn). Because the CAM 100 in this example uses dual ended logic, the local pair of bit lines 112 carry differential data representing a single bit of data, and the local pair of compare lines 114 carry differential data representing a single bit of comparison data.
Each CAM cell 110 in a row is connected to a word line 116 and a match line 118. The word line 116 enables read and write access to the CAM cells 110. The match line 118 provides an output for a comparison result. The multiple match lines 118 feed into an encoder 120. Typically, the encoder 120 generates three output signals. A line designated HT is asserted high when one of the words stored in the CAM matches the comparand. A line designated AD, outputs a set of signals representing the address of the matched word. A line designated MLT is asserted high when multiple stored words match the comparand.
In some conventional designs, a priority encoder is used in place of the encoder 120. The priority encoder functions in the same way except that in addition to asserting the MLT line high when multiple stored words match the comparand, it also outputs a set of signals on the AD line representing the address of the matched word in the lowest position in the CAM. Moreover, in some conventional designs a dynamic random access memory (DRAM) or a static random access memory (SRAM) are employed in place of the encoder 120, thereby resulting in a CAM-DRAM or CAM-SRAM configuration, as is well known in the art.
CAM cell 110a in FIG. 1 is an expanded view of a single CAM cell 110, as may be found in a typical CAM. CAM cell 110a includes a CAM memory core cell 130, a xe2x80x9ccomparator blockxe2x80x9d comprising two N-channel field effect transistors (FET) 132 and 134, and a match line N-channel FET 136. The CAM memory core cell 130 has two outputs designated C and CN, which are differential outputs representing a single bit of data stored in CAM memory core cell 130. The first N-channel FET 132 connects to the positive compare line K and is gated by the output C. The second N-channel FET 134 connects to the negative compare line KN and is gated by the output CN. The output of the comparator block gates the match line N-channel FET 136, thereby transmitting a comparison result for CAM cell 110a to the match line 118 during a compare operation.
Alternative conventional designs involve transmission of a comparison result to a match line in a wired-NOR configuration. In these designs, the first N-channel FET 112 would be gated by CN, and the second N-channel FET 134 would be gated by C. The match line N-channel FET 136 remains gated by the output of the comparator block, but instead of connecting a match line input with a match line output, it connects the match line 118 with a ground. In this fashion, the match line 118 is pulled low whenever a mismatch between the stored word and the comparand occurs. This configuration results in a fast comparison, but every time there is a mismatch, the match lines must be discharged and then charged up again. For large CAMs, this configuration results in excessive power consumption.
FIG. 1 further shows an expanded view of an example of a CAM memory core cell 130a. In a typical configuration,the CAM memory core cell 130a includes a static memory element 140 and two access N-channel FETs 142 and 144. The static memory element 140 typically consists of two cross-coupled inverters.
While the CAM design represented by the CAM 100 can be used to construct relatively high-speed, large-capacity CAMs, in certain applications it may experience limitations. For example, when the CAM 100 becomes very large, the chances that multiple hits will occur during a compare operation increases. When this happens, the word data stored in the CAM 100 needs to be checked and updated, which can be a time consuming process. Without word-wise masking capability, the data in the CAM word that matched would need to be physically overwritten. Even with word-wise masking capability, it could take multiple cycles to find the right data if more than two hits occur during a compare operation.
In some CAM applications, only particular fields of the word data stored in the CAM need to be checked. For example, if the CAM is getting read requests from multiple devices, but the CAM only needs to check a certain small subset of those read requests, it requires the ability to mask out some read requests and find the particular data it cares about. In these CAM applications, the chances of multiple hits in the CAM increase significantly.
One technique for attempting to provide for masking is to add a xe2x80x9cvalid bitxe2x80x9d to each CAM cell. By adding a valid bit storage capacity to each CAM cell, selective bit-wise and word-wise comparisons are enabled. The valid bit storage capacity requires the addition of a second CAM memory core cell to the CAM cell. Multiple examples of such a design are shown in U.S. Pat. No. 6,044,005 entitled xe2x80x9cContent Addressable Memory Storage Device.xe2x80x9d But once the second CAM memory core cell is added to the CAM cell, the CAM cell becomes significantly larger and consumes a great deal of power. When an application requires a very deep CAM, as is common in modern communications applications, the result is a large and power-hungry CAM.
In addition, the conventional schemes for implementing a match line chain do not work well for CAMs that need to operate at lower voltages. Each time the match line goes through N-channel FET 136 inside each CAM cell, a threshold and a body effect of the N-channel FET 136 need to be regenerated. Thus, the match line will not reach the power supply voltage level VDD upon a match, but will only reach a lower voltage, VDD minus a threshold and minus a body effect voltage. Devices that require deep CAMs, such as modern telecommunications equipment, are continually being designed with more restrictive power consumption constraints and thus need to operate at lower voltages. As the voltage used for running the CAM goes down, such conventional CAM designs impair performance.
It would therefore be advantageous to provide a CAM cell design and a method of pre-charge and comparison timing to solve the problems with conventional CAM design.
The invention is directed in one aspect to a content addressable memory cell for use in a content addressable memory (CAM).
In one embodiment, a CAM cell includes a comparison bit line and a first CAM memory core cell configured to store data. The CAM cell further includes comparison circuitry and a first P-channel transistor configured to communicate a comparison result to a match line using the Miller effect. The comparison circuitry is coupled with the comparison bit line and the first CAM memory core cell, and the first P-channel transistor is coupled with the comparison circuitry.
In another embodiment, a CAM cell for use in a CAM having fall bit-wise and word-wise masking capability includes a positive comparison bit line, a negative comparison bit line, a first dual-ended CAM memory core cell configured to store data, and a second dual-ended CAM memory core cell configured to store masking data. The CAM cell further includes comparison circuitry, a first P-channel transistor configured to communicate a comparison result to a match line using the Miller effect, and a second P-channel transistor configured to communicate a masked state to the match line. The comparison circuitry is coupled with the positive comparison bit line, the negative comparison bit line, and the first CAM memory core cell. The first P-channel transistor is coupled with the comparison circuitry, and the second P-channel transistor is coupled with the second CAM memory core cell.
A method is also provided for operating a CAM having CAM cells that employ P-channel transistors to communicate comparison results to match lines. By operating the CAM in this fashion, faster operation of the CAM at lower voltages may be experienced. The method preferably includes the step of discharging a match line input to VSS, thereby causing intermediate nodes on a match line to discharge to a voltage level just above VSS during normal operation. The intermediate nodes lie between CAM cells having P-channel transistors connected in series on the match line. The method preferably further includes transitioning comparison inputs to the CAM cells to initiate a comparison operation. The transitioning occurs at substantially the same time for each of the comparison inputs. The method preferably further includes the steps of charging the match line input to VDD during the comparison operation, and utilizing the Miller effect to stop a signal flow from passing through one of the CAM cells when that CAM cell identifies a mismatch for the comparison operation.
A method of designing a CAM to allow faster operation at lower voltages is also provided. The method preferably includes the step of connecting CAM cells that employ P-channel transistors to communicate comparison results to match lines such that, during normal operation, intermediate nodes between CAM cells in a match line chain do not drop all the way to VSS before a compare operation. The method preferably flirter includes coupling a match line input with a pre-charge line and with a match line for the CAM cells in the match line chain such that the match line input is electrically switched from a connection with VSS to a connection with VDD during the compare operation. The method preferably further includes the step of designing driver circuits that allow transitioning of comparison inputs to the CAM cells in the match line chain to be performed nearly simultaneously. The driver circuits are coupled with the pre-charge line such that a Miller effect may be used during the compare operation to stop a signal flow from passing through one of the CAM cells in the match line chain when that CAM cell identifies a mismatch.
Further features and advantages of the invention as well as the structure and operation of various embodiments of the invention are described in detail below with reference to the accompanying drawings.